/*
 * @lc app=leetcode.cn id=1981 lang=typescript
 *
 * [1981] 最小化目标值与所选元素的差
 */

// @lc code=start
function minimizeTheDifference(mat: number[][], target: number): number {
  const m = mat.length;
  const maps: Set<number>[] = [new Set(), new Set()];
  // 初始化
  let sum = Number.MIN_VALUE;
  for (const num of mat[0]) {
    maps[0].add(num);
    sum = Math.max(sum, num);
  }
  // 遍历
  for (let i = 1; i < m; i++) {
    let idx = i % 2;
    let preIdx = (i - 1) % 2;
    // 每次清空当前哈希表，将新的结果通过上一个哈希表计算获得
    maps[idx].clear();
    // 将当前行和之前所有行的最大值累加，做为遍历的边界
    sum += Math.max(...mat[i]);
    // 遍历，看看当前数字能否加入到当前行的计算结果中
    // 遍历区间最小是每行都是1的情况，最大就是每行的最大值累加
    for (let j = i + 1; j <= sum; j++) {
      for (const num of mat[i]) {
        // 能够凑成 j ，就加入到当前行的计算结果中，然后跳出当前循环
        // 避免重复插入
        if (maps[preIdx].has(j - num)) {
          maps[idx].add(j);
          break;
        }
      }
    }
  }
  // 找到最小差值
  let ans = Number.MAX_VALUE;
  for (const num of maps[(m - 1) % 2]) {
    ans = Math.min(ans, Math.abs(num - target));
  }

  return ans;
}
// @lc code=end
